Lena e iLena

Existem algumas imagens que são icônicas. São tão conhecidas, que só com uma descrição simples você já sabe de qual imagem eu estou falando. O rosto do Che Guevara, a Marilyn com a saia levantada, o chinesinho parando os tanques: todos conhecem essas imagens.

Agora, se você for um estudioso do processamento digital de imagens, as suas imagens icônicas são outras. Para poder comparar algoritmos, nós usamos uma série de imagens padronizadas, como o mandrill e as pimentas. Mas, dessas imagens, nenhuma é tão conhecida como a Lena:

Lena

Há quem diga que a imagem da Lena ficou tão famosa entre os cientistas por ser uma imagem complexa o suficiente pra testar qualquer algoritmo: ela tem freqüências baixas e altas, texturas complexas, faixa dinâmica larga. A minha teoria é mais prosaica: se você vai ter que ficar olhando pra mesma imagem por meses, uma mulher bonita é melhor que um babuíno de nariz vermelho :)

Mas a imagem da Lena tem um segredo que nem todos conhecem. Quando eu descobri a origem da imagem, fiquei doido pra conseguir uma cópia original da fonte de onde essa imagem saiu. E depois de anos procurando, finalmente consegui:

Clique na imagem pra ver a versão completa, NSFW

Sim, a imagem usada por cientistas do mundo todo, na verdade, é um centerfold da Playboy!

Essa edição é a Playboy americana de novembro de 1972. Eu corajosamente a comprei no ebay, mesmo com os avisos que diziam "warning: pages may be sticky". Foi um ótimo negócio, o vendedor me vendeu uma Playboy usada, e eu comprei um pedaço da história da computação :)

A origem da imagem é curiosa. Conta-se que o pesquisador tinha um paper pra entregar no dia seguinte, e precisava de uma imagem com urgência. Ele acabou digitalizando a primeira revista que achou em sua mesa, a edição da Playboy com a Lena, que, curiosamente, também foi a edição mais vendida da história da revista. Ele não contou pra ninguém a origem da imagem, e por anos muitos usaram a imagem sem conhecer a história dela.

Isso acabou gerando um problema quando a Playboy descobriu que uma das suas imagens estava sendo copiada indiscriminadamente por aí. Inicialmente, ela tentou impedir o uso da imagem, mas depois acabou descobrindo que era boa propaganda, e hoje em dia a diretoria da revista faz vista grossa para o assunto.

Por outro lado, como a imagem ainda tem copyright, nunca se sabe se um dia a diretoria não vai mudar de idéia e vetar novamente o uso. Se você precisa de uma nova imagem de teste, agora tem uma nova solução! A minha esposa (ilustradora, modelo e atriz), fez um remake da imagem da Lena, e disponibilizou com a licença Creative Commons Attribution-Share Alike. E se você usar a imagem em algum paper, eu ainda posso fazer um peer review na faixa pra você.

iLena

Obviamente, a versão original dessa imagem só eu tenho :)

O Desentortador

Eu confesso que fiquei apreensivo quando soube que teria que passar vários meses na Califórnia. Afinal, Mountain View não é nenhuma San Francisco, eu tinha medo de morrer de tédio enquanto estivesse lá. Mas, felizmente, meu medo esvaiu-se quando eu descobri O Sebo!

O Sebo é um lugar lindo e maravilhoso onde você pode comprar The Diamond Age por apenas 50 cents, e inúmeros outros livros por preços tão baixos quanto esse. Na foto acima, você pode ver uma pequena porção do paraíso, mostrando apenas a parte de sci-fi, e apenas os autores das letras D até L. Sim, O Sebo é um lugar gigante e com diversão garantida pra várias semanas.

Depois de encher a mochila com livros, eu tive vontade de tirar uma foto deles pra mandar pros amigos. Foi então que eu tive um problema. Eu estava tentando tirar a foto à noite, e se eu colocasse a câmera exatamente sobre o livro, o flash estourava, e tudo que saía na foto era um grande borrão branco. Sem flash também não funcionava, ficava escuro demais pra câmera conseguir estabilizar a imagem.

Eu resolvi esse problema inclinando a câmera em relação ao plano do livro. Isso certamente resolve o problema do flash, mas em compensação o livro fica torto na foto. Uma solução simples seria simplesmente esperar amanhecer e tirar a foto do livro com a luz do dia. Mas é claro que optei por uma alternativa mais bizarra :) Resolvi escrever um software que desentortasse a foto do livro automaticamente!

Pra isso, vamos começar com a foto original do livro torto:


Pra começar o desentortamento, a primeira coisa que precisamos descobrir é onde estão as bordas do livro, que vão definir como vai ser a rotação que iremos fazer. Achar as bordas é fácil, basta identificar a fronteira entre livro e não-livro. Para isso, eu usei um algoritmo simples de crescimento de região:


Não ficou a coisa mais perfeita do mundo: está cheio de ruído em volta, e o algoritmo ainda vazou pra dentro do livro (a mesa era marrom, da mesma cor do urso na capa, e ele se perdeu com isso).

A boa notícia é que nenhuma dessas coisas importa! O que eu quero achar são as bordas, que tem uma direção preferencial bem determinada. Se eu utilizar a transformada de Hough, tanto o ruído quanto o vazamento devem sumir, e de fato é o que acontece. Essa é a transformada da imagem acima:


A transformada de Hough leva retas em pontos, então as quatro retas que formam a borda do livro viram quatro pontos bem brilhantes na transformada. É simples agora usar um threshold pra identificar esses pontos, e aplicar a transformada inversa pra achar as retas na imagem original:

Nessa imagem eu tracei linhas vermelhas nas retas identificadas pela transformada. Estamos quase lá, mas um problema da transformada de Hough é que ela acha retas, e não segmentos de retas. O que me interessa na verdade são os vértices do livro, então eu preciso achar as intersecções entre essas retas.

O detalhe é que quatro retas em posição geral determinam seis pontos, e não quatro. No caso da imagem acima, por exemplo, as retas verticais se encontram no ponto de fuga, bem acima do livro. A solução que eu usei foi adotar uma gambiarra heurística de considerar apenas os quatro pontos mais próximos do centro da imagem original. Além disso, também é legal converter os pontos pra coordenadas polares em relação ao centro da imagem, assim podemos ordená-los pelo ângulo.

Tendo os quatro vértices, agora é só aplicar uma transformação afim na imagem que a leve pra um retângulo e o trabalho está terminado né? Quem dera hehe. Se você fizer isso, a imagem fica com uma deformação não-linear: achatada na parte de cima, e esticada na parte de baixo.


Na década de 90, todo guri metido a programador fazia sua própria engine 3D pra imitar o Doom e o Quake; quem passou por essa época reconhece na hora a origem da deformação. O que está acontecendo é um problema de inverse perspective-correct texture mapping. A perspectiva introduz um fator do tipo 1/z na sua textura, e você precisa compensar isso quando for mapear na imagem. Vamos fazer a correção de perspectiva então:


Yatta! Finalmente temos a imagem final, desentortada como queríamos :) Na verdade, nós desentortamos a imagem em um único eixo, dá pra ver claramente que além do pitch essa imagem também precisava de correção no roll, mas isso fica como exercício pro leitor.

Eu implementei todos os passos descritos acima em python, usando a biblioteca PIL. Ele roda rapidinho, uns 3s por imagem apenas. O source é o abaixo:

Source do desentortador em python

Se alguém quiser reaproveitar o código pra fazer alguma coisa útil com ele (hehe), sinta-se à vontade. Salvo indicação em contrário, todos os programas desse blog são disponibilizados sob a Licença Crowley (Do what you want shall be the whole of the License).

PS: Ah sim, como vocês repararam, a partir de agora o blog vai ter desenhos também! Eu gostaria de dizer que se funcionou pro Chrome, deve funcionar pra mim também; mas a verdade é que a Aleph já fazia a mesma coisa lá na década de 80 :)

MapReduce is running

Quando eu era estagiário na década de 90, um dos meus primeiros projetos envolvia computação paralela. O projeto Visible Human tinha acabado de fatiar os primeiros espécimes, e nosso grupo estava doidinho pra fazer ray-tracing do volume de dados. Mas o volume de dados era grande demais pros padrões da época, e única saída foi importar uma Meiko com dez processadores, pra dar conta do trabalho.

(Meiko, aliás, que tem uma história curiosa. Apesar de ter dez processadores, só conseguíamos rodar processos em nove deles, tinha um que não funcionava de jeito nenhum. Depois de muitas ligações pro suporte, resolvemos desmontar a máquina pra ver se tinha alguma coisa errada no hardware, e, surpresa, entre o pente de memória e o conector na motherboard tinha um mosquito preso. Sim, aquela cpu tinha um bug :)

Mas programar diretamente a comunicação entre os processadores, com PVM ou MPI, é trabalho demais. A nossa solução foi escrever uma camada intermediária que abstraía a parte de comunicação e fazia o paralelismo de modo implícito. Nossa biblioteca era customizada pra visualização volumétrica paralela, mas hoje em dia a mesma abordagem é feita de maneira mais genérica, por pacotes como o Hadoop e o MapReduce, sendo que esse último eu uso bastante hoje em dia.

Mas, mesmo paralelizando o processamento, o melhor que uma abordagem dessas consegue é um ganho linear no número de processadores. Se o tamanho do seu volume de dados precisa daqueles prefixos que vêm depois do giga, então até o MapReduce pode demorar um pouco pra rodar. Nesse fim de semana eu encontrei o Randall Munroe, e pedi pra ele ilustrar como é um MapReduce na prática :)


Eu também aproveitei pra filmar o Randall enquanto ele desenhava esse sketch. Como o estilo dele é, hum, minimalista, isso o torna o único cartunista que eu conheço que consegue ser mais rápido que o Aragonés: